#include <ctime>
#include <endian.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/select.h>
#include <time.h>
#include "0.sort_test.h"

#define threshold 16

void quick_sort(int *arr, int l, int r){
    if(r - l <= 2){
        if(r - l <= 1) return;
        if(arr[l] > arr[l + 1]) swap(arr[l], arr[l + 1]);
        return;
    }
    //patition
    int x = l, y = r - 1, z = arr[l];
    while(x < y){
        while(x < y && z <= arr[y]) --y;
        if(x < y) arr[x++] = arr[y];
        while(x < y && arr[x] <= z) ++x;
        if(x < y) arr[y--] = arr[x];
    }
    arr[x] = z;
    quick_sort(arr, l, x);
    quick_sort(arr, x + 1, r);
    return;
}

void quick_sort_v1(int *arr, int l, int r){
    if(r - l <= 2){
        if(r - l <= 1) return;
        if(arr[l] > arr[l + 1]) swap(arr[l], arr[l + 1]);
        return;
    }
    //patition
    int x = l, y = r - 1, z = arr[l];
    do{
        while(arr[x] < z) ++x;
        while(arr[y] > z) --y;
        if(x <= y){
            swap(arr[x], arr[y]);
            ++x;
            --y;
        }
    }while(x <= y);
    quick_sort_v1(arr, l, y + 1);
    quick_sort_v1(arr, x, r);
    return;
}

int three_point_select(int a, int b, int c){
    if(a > b) swap(a, b);
    if(a > c) swap(a, c);
    if(b > c) swap(b, c);
    return b;
}

void quick_sort_v2(int *arr, int l, int r){
    if(r - l <= 2){
        if(r - l <= 1) return;
        if(arr[l] > arr[l + 1]) swap(arr[l], arr[l + 1]);
        return;
    }
    //patition
    int x = l, y = r - 1;
    int z = three_point_select(arr[l], arr[r -1], arr[(l + r) / 2]);
    do{
        while(arr[x] < z) ++x;
        while(arr[y] > z) --y;
        if(x <= y){
            swap(arr[x], arr[y]);
            ++x;
            --y;
        }
    }while(x <= y);
    quick_sort_v2(arr, l, y + 1);
    quick_sort_v2(arr, x, r);
    return;
}

void quick_sort_v3(int *arr, int l, int r){
    if(r - l <= 2){
        if(r - l <= 1) return;
        if(arr[l] > arr[l + 1]) swap(arr[l], arr[l + 1]);
        return;
    }
    //patition
    while(l < r){
        int x = l, y = r - 1;
        int z = three_point_select(
            arr[l], 
            arr[r - 1], 
            arr[(l + r) / 2]);
        do{
            while(arr[x] < z) ++x;
            while(arr[y] > z) --y;
            if(x <= y){
                swap(arr[x], arr[y]);
                ++x;
                --y;
            }
        }while(x <= y);
        quick_sort_v3(arr, l, y + 1);
        l = x;
    }
    return;
}

void unguarded_insert_sort(int *arr, int l, int r){
    int idx = l;
    for(int i = l + 1; i < r; i++){
        if(arr[i] < arr[idx]) idx = i;
    }
    while(idx > l){
        swap(arr[idx], arr[idx - 1]);
        idx -= 1;
    }
    for(int i = l + 1; i < r; i++){
		int j = i;
        while(arr[j] < arr[j - 1]){
            swap(arr[j], arr[j - 1]);
            j -= 1;
        }
	}
    
    return;
}

void __quick_sort_v4(int *arr, int l, int r) {
    while (r - l > threshold) {
        // partition
        int x = l, y = r - 1;
        int z = three_point_select(
            arr[l], 
            arr[r - 1], 
            arr[(l + r) / 2]
        );
        do {
            while (arr[x] < z) ++x;
            while (arr[y] > z) --y;
            if (x <= y) {
                swap(arr[x], arr[y]);
                ++x, --y;
            }
        } while (x <= y);    
        __quick_sort_v4(arr, l, y + 1); // left
        l = x;
    }
    return ;
}

void quick_sort_v4(int *arr, int l, int r) {
    __quick_sort_v4(arr, l, r);
    unguarded_insert_sort(arr, l, r);
    return ;
}

void output(int *arr, int l, int r){
    printf("\n");
	for(int i = l; i <= r; i++){
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int patition(int *arr, int l, int r){
    int pivot = arr[l];
    int j = l;
    for(int i = l + 1; i <= r; i++){
        if(arr[i] <= pivot){
            j += 1;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[l], arr[j]);
    return j;
}

int patition2(int *arr, int l, int r){
    int pivot = arr[r];
    int i = l;
    for(int j = l; j < r; j++){
        if(arr[j] <= pivot){
            swap(arr[i], arr[j]);
            i++;
        }
    }
    swap(arr[i], arr[r]);
    return i;
}

int patition3(int *arr, int l, int r){
    int pivot = arr[l];
    int i = r, j = l + 1;
    while(1){
        while((j <= i) && (arr[j] <= pivot)) j++;
        while((j <= i) && (arr[i] >= pivot)) i--;
        if(j >= i) break;
        swap(arr[i], arr[j]);
    }
    swap(arr[l], arr[i]);
    return i;
}

int patition4(int *arr, int l, int r){
    int pivot = arr[r];
    int left = l, right = r;
    while(left < right){
        while(left < right && arr[left] <= pivot) left++;
        arr[right] = arr[left];
        while(left < right && arr[right] >= pivot) right--;
        arr[left] = arr[right];
    }
    arr[right] = pivot;
    return right;
}

void my_quick_sort(int *arr, int l, int r){
    if(l >= r) return;
    int pivotIdx = patition4(arr, l, r);
    my_quick_sort(arr, l, pivotIdx - 1);
    my_quick_sort(arr, pivotIdx + 1, r);
    return;
}

void mytest(){
    int a[] = {8, 1, 3, 2, 7, 6, 4};
    int *arr = a;
    my_quick_sort(arr, 0, 6);
    output(arr, 0, 6);
}

int main(){
    int *arr_s = getRandData(SMALL_DATA_N);
    int *arr_b = getRandData(BIG_DATA_N);
    TEST(quick_sort, arr_s, SMALL_DATA_N);
    TEST(quick_sort, arr_b, BIG_DATA_N);
    TEST(quick_sort_v1, arr_b, BIG_DATA_N);
    TEST(quick_sort_v2, arr_b, BIG_DATA_N);
    TEST(quick_sort_v3, arr_b, BIG_DATA_N);
    TEST(quick_sort_v4, arr_b, BIG_DATA_N);
    TEST(my_quick_sort, arr_b, BIG_DATA_N);
    free(arr_s);
    free(arr_b);
    // mytest();
    return 0;
}